package com.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,1]
 * 输出: 1
 * 示例 2:
 * <p>
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 只出现一次的数字 {

	/**
	 * 方法一：使用集合Set解决
	 */
	public static int singleNumber(int[] nums) {
		Set<Integer> set = new HashSet();
		for (int num : nums) {
			if (!set.add(num)) {
				set.remove(num);
			}
		}
		return (int) set.toArray()[0];
	}

	/**
	 * 方法二：采用异或（两值相同异或为 0；两值不同异或为 1）
	 * a ^ a = 0
	 * a ^ 0 = a
	 * a ^ b = b ^ a
	 */
	public static int singleNumber1(int[] nums) {
		int result = 0;
		for (int num : nums) {
			result ^= num;
		}
		return result;
	}

	public static void main(String[] args) {
		int[] arr = {2, 2, 3};
		System.out.println(singleNumber1(arr));
	}
}
